/*
 * Project: Code
 * File Created at 2024/1/13
 @Type Coin_change.java
 @author Goodwin
 * Website : https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
*/

package Dynamic_Program;
import java.util.Arrays;

public class Coin_change {
    public int soultion(int[] coins, int amount){
        int[] dp = new int[amount+2];
        dp[0] = 0;
        Arrays.fill(dp, amount+1);
//        todo ： dp[i] 表示 i 需要的最小零钱数
        for(int i=0;i<coins.length;i++){
            dp[coins[i]] = 1;
        }
        for (int j = 1; j <= amount; j++) {
            for (int i = 0; i < coins.length; i++) {
                if(j-coins[i]>=0){
                    dp[j] = Math.min(dp[j], dp[ j-coins[i] ] +1);
                }
            }
        }
        return dp[amount] > amount ? -1:dp[amount];
     }
}












































